\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}
\usepackage{psfig}
\usepackage{url}
\usepackage{algorithm}
\usepackage{algorithmic}
% \usepackage[pdftex]{graphicx}
\usepackage{subfig}
\usepackage{color}
\usepackage{xcolor}
\usepackage{listings}

\usepackage{caption}
\DeclareCaptionFont{white}{\color{white}}
\DeclareCaptionFormat{listing}{\colorbox{gray}{\parbox{\textwidth}{#1#2#3}}}
\captionsetup[lstlisting]{format=listing,labelfont=white,textfont=white}




% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt \advance \topmargin by -\headheight \advance \topmargin by
-\headsep \textheight 8.9in \oddsidemargin 0pt \evensidemargin \oddsidemargin
\marginparwidth 0.5in \textwidth 6.5in

\parindent 0in \parskip 1.5ex
% \renewcommand{\baselinestretch}{1.25}

\begin{document}

\title{Truthfulness Verification System}

\author{
Tathagata Dasgupta, ABM Musa\\
Email: \{tdasgu2, amusa2\}@uic.edu\\
URL: http://code.google.com/p/tverifier }

\date{}
\maketitle


%\section{Progress Summary}
%
%
%{\em Mar 29 to Apr 12}
%See page~[\pageref{Mar29toApr12}] of section~\ref{sec:UseOfWikipedia}
%\begin{itemize}
%\item Extraction of meaningful entities(noun phrase) in topic unit and dount unit by checking all combination of content words
%\item Ranking based on co-occurence of content words in the interesction of bag of words generated from wiki-articles. 
%\item Ranking based on co-occurence of content words in the sentences generated from wiki-articles. 
%\end{itemize}
%
%
%{\em Mar 9 to Mar 29}
%\begin{itemize}
%\item Formulated the initial steps for feature extraction for each doubt unit using Wikipedia. See page~[\pageref{March9to29}] of section~\ref{sec:UseOfWikipedia}
%\end{itemize} 
%{\em Feb 23 to Mar 9} 
%\begin{itemize}
%\item Formulated the procedure of truthfulness verification in a more structured way
%\item As a result of the procedure formulation, the sections Step-by-step Algorithm for Truthfulness and Verification Examples of Truthfulness Verification are written in a complete revised way compared to the proposal
%\item Apart from getting out feet wet with the MQL api, the daunting task is to develop generalized framework that is flexible enough to fit the wide variety of sentences into the rigid structure of Freebase. The learning cure is steep, given the richness and massive size of documentation. Though we are groping in dark currently, we are hopeful that the pieces of the puzzle with soon fit in.
%\item Looked into applicability of POS tagger in the context of our problem and found it useful for constructing freebase queries
%\item Got some initial promising results by exploring different options such as Wikipedia, answer.com beyond Freebase ontologies. 
%\item Worked on porting of existing T-verifier code to linux. The original T-verifier code is for windows only and not generic enough at this moment. We also contacted with the student author about the problems we are facing to port the code to linux. We hope to resolve it soon.
%\end{itemize}


\section{Introduction}
Web has became the most prevalent source of information now a days. However, many
information on the web is untruthful. Also because of the widespread reach of
web, sometimes web is used to propagate untruthful facts for social and political
reasons. Hence with the increasingly use of web as information source,
verification of information truthfulness became an important facet to consider.

The popular search engines extract information from web based on keywords and
metadata without considering the truthfulness of the facts. Also, there have been
not much research in this area. To our best knowledge, the most recent work on this area is T-verifier  \cite{tverifier}, which uses results from search engines
to verify truthfulness of statements. T-verifier performs very well on the
test-dataset. However, T-verifier has some problems with the overall approach to
verify the truthfulness of statements and there is room for improvement. In this
work, we will extend the T-verifier system so that it's weaknesses can be
resolved to get a more robust truthfulness verification system.


\section{Current System}
Current system for truthfulness verification is called T-verifier
\cite{tverifier}, which uses two phase methods for truthfulness verification of
statements. Each of these two phases rely heavily on search results returned by
popular search engines. T-verifier takes the doubtful statements ($DS$) as input
from the user along with the doubtful unit (DU). Phrase after removing DU from $DS$
is called topic unit (TU).

At the first phase, T-verifier generates alternative statements by supplying
$TU$ to search engine and collecting the relevant alternate $DU$-s. However,
from basic web search may result in lot of alternate $DU$-s that are not semantically or
logically relevant to the original $DS$. Hence, T-verifier uses combination of
seven features to rank alternate $DU$-s. These features primarily exploit the facts
that relevant alternative units frequently co-occur, people often mention both
misconception and truthful conception together, data-type matching, and
sense-closeness. T-verifier chooses top 5 alternative statements based on top 5
alternate $DU$-s obtained in this phase.

At the second phase, top 5 alternative statements from phase 1 is supplied to the
search engine again. Then the returned searched result is ranked by multiple
rankers such as Alternative Unit Ranker, Hits ranker, Text-feature Ranker, Domain
Authority Ranker etc. Then all those ranks are merged to form an overall ranking
among the alternate statements and top statement in this final merged ranking is
considered as truthful statement.

% We are currently working to get the T-verifier code running on our systems,
% with inputs from Xian Li. So the descriptions below lacks some required details
% and makes some assumptions.   As of now T-Verifier produces 5 alternative
% statements once it is provided with a doubtful statement ($DS$), a doubtful unit
% (DU), data type of the unit etc in the first phase. Though these sentences
% produced are quite accurate, the facility to pinpoint the correct alternative
% does exist yet. The project goal, may be formulated as:  "Extract information
% from Wikipedia and ontologies ( such as Yago, DBpedia and Freebase) which helps
% to verify truthfulness of statements. Describe the extraction algorithm and how
% the information can be utilized to assist statement truthfulness verification."

\section{Problems with Current System}
Although results from the tested dataset achieves good performance (90\%
accuracy), failing of T-verifier for some statements shows that it has some
inherent problems and there is room for improvement.

First, T-verifier assumes that truthful statements will be more propagated in the
web compared to the untruthful statement. However, this may be not true in
general because of intended and planned propaganda for establishing some
untruthful statements. This kind of propagandas are even becoming more common now
a days due to widespread reach of Internet. T-verifier also showed that \emph{"Hillary
Clinton is the President of United States"} has more hits than \emph{"Hillary Clinton is
the Secretary of State"}. Although T-verifier was able to find the correct
statement in this case using multiple ranks together, in general the untruthful
statement can be prevalent in the web compared to truthful statements.

Second, T-verifier do not use the reputation of the information source.
T-verifier uses only search results returned by the search engine irrespective of
the origin and believability of the information origin. Hence there is room for
improvement here to give more weight to the information obtained from trustworthy
sources such as Wikipedia.


\section{Proposed System}
\label{sec:UseOfWikipedia}
We have tried two approaches for using the Wikipedia. In both we utilize the content words to identify articles and there upon treat them separately. In the first approach we treat the articles as bag of words and do not consider the sentence structure and in the next approach we retain the logical structure of each sentence and try to infer from word overlaps.
%When we do a regular expression search of the $DU$ "Les Paul" in these two sentences, we do not get any match. Hence we can conclude that the statement is not true. 
 
%Moreover, we can also look for truthful statement by using those above extracted sentences. Using a better POS tagger and Named entity extractor (may those offered by LingPipe or Standford Named Entity Tagger) we cant extract the noun phrases and create the list of possible $AU$ that matches the data type of the $DU$. A comparison with the $AU$-s generated by the exisiting version of the T-verifier will give us allow us to do a fine grained analysis.

\label{Mar29toApr12}

\subsection{Bag of words}
In the bag of words method, we are exploiting the fact that for true sentence we will have high content word match between pages obtained from topic unit and alternate units. Overall steps of this method are described below:
\begin{itemize}
\item For all possible k-grams $(k=1,2,3,...,topic\_unit\_length)$ of topic unit we find relevant wikipedia page using wikipedia search API. Although it may seems that taking all possible k-grams will introduce noise in the retrieved data, this is not the case because there will be no pages for irrelevant k-gram consisting of irrelevant combination of words. Now for each possible k-gram we may get a Wikipedia page directly or we may go need to disambiguate if that k-gram refers to multiple possible pages in Wikipedia. If we get a single page without any ambiguation then we take that page. However, if we need to disambiguate then we look into all possible wikipedia pages and disambiguate them using highest intersection of words of topic unit and description of the wikipedia page for the disambiguation link. Here we take all words except the k-gram for which we are disambiguating as a set of words for intersection. So assume that at the end of this step we get $n$ wikipedia pages either directly or through disambiguation.

\item Now for each of the five alternative units generated by the T-verifier we also find a wikipedia page. Here also we may get a Wikipedia page directly or we may need to disambiguate if there are multiple possible pages. If we need disambiguation then we disambiguate using same approach described previously i.e. maximal intersection of words between the description of disambiguation link and words of topic unit.

\item We have five Wikipedia pages for each of the alternative units now and $n$ pages from topic unit. We generate bag of words i.e. content words for all the five pages for alternate units and $n$ pages for topic unit.

\item Now for each of the page corresponding to alternate units we count intersection of words for each $n$ pages for topic unit and take sum of  intersection count for an alternate unit page and $n$ topic unit page. Hence at this step we have a count value associated with each of the alternate unit and we rank all the alternate units according to this value to produce truth confidence or rank for all five alternate units.
\end{itemize}

Pseudo-code for Bag of words ranking is given below. Listing \ref{alg:BagOfWords} produces the ranking for all five alternative units following the procedure described above. It uses Listing \ref{alg:findwikiarticles} to generate k-grams and find relevant Wikipedia pages and Listing \ref{alg:disambiguate} to disambiguate among alternative pages using intersection of words between topic unit and description of disambiguation link for alternative page

%\begin{algorithm}
%\small
%\caption{Bag of Words (Algorithm 1)}
%\label{alg:AssignScore1} 
%\begin{algorithmic}
%\STATE \textbf{Description}: Given the alternate units generated by the current T-verifier system, rank the units in descending order of truthfulness using Wikipedia
%\STATE \textbf{Input}: alter\_units.txt genereated by T-verifier. Each line in this file is a tuple containing the sentence id, the alternate units generated and the topic unit.
%\STATE \textbf{Output}: Ranked alter\_units 
%\FOR {each sentence $s_{i}$}
%	\STATE $tu_{i}$ = topic unit string
%	\STATE $s_{i}.tu\_list$ = find\_wikiarticles\_tu($tu_{s_{i}}$)
%		
%	\FOR {each alternate unit $s_{i}.au_{j}$ in $s_{i}.au\_list$ }
%		\STATE $bow_{s_{i}.au_{j}}$ = find\_wikiarticles\_au($s_{i}.au_{j}$)
%	\ENDFOR
%	\FOR {each alternate unit $s_{i}.au_{j}$ in $s_{i}.au\_list$ }
%		\STATE $bow_{s_{i}.au_{j}}$ = find\_wikiarticles\_au($s_{i}.au_{j}$)
%	\ENDFOR	
%	%\FOR{every wiki\_article $w_{p}$ in $list_wiki_articles_au_{s_{i}}$ }
%	%	$bow_w_{p}$ = generate\_bag\_of\_words($w_{p}$)	
%	%	\FOR {every wiki\_article $w_{j}$ in $list_wiki_articles_tu_{j}$  }	
%	%	\ENDFOR
%	%\ENDFOR
%\ENDFOR
%
%
%\end{algorithmic}
%\end{algorithm}
%


\begin{algorithm}
\small
\caption{Bag of Words (Ranking Algorithm 1)}
\label{alg:BagOfWords}
\begin{algorithmic}
\STATE \textbf{Description}: Given the alternate units generated by
the current T-verifier system, rank the units in descending order of
truthfulness using Wikipedia
\STATE \textbf{Input}: alter\_units.txt genereated by T-verifier. Each
line in this file is a tuple containing the sentence id, the alternate
units generated and the topic unit.
\STATE \textbf{Output}: Ranked alter\_units
\FOR {each sentence $s_{i}$}
       \STATE $tu_{s_{i}}$ = topic unit string
       \STATE $s_{i}.au\_list$ = alternate units generated by T-verifier
       \STATE $s_{i}.tu\_list$ = find\_wikiarticles\_tu($tu_{s_{i}}$)

       \FOR {each alternate unit $s_{i}.au_{j}$ in $s_{i}.au\_list$ }
               \STATE $w_{s_{i}.au_{j}}$ = find\_wikiarticles\_au($s_{i}.au_{j}$)
               \IF {$w_{s_{i}.au_{j}}$ == $\phi$}
                       \STATE skip to processing next $w_{s_{i}.au_{j}}$
               \ENDIF
               \IF {$w_{s_{i}.au_{j}}$ is diambiguation page}
                       \STATE $w_{s_{i}.au_{j}}$ = disambiguate($w_{s_{i}.au_{j}}$)
                       \STATE $bow_{s_{i}.au_{j}}$ = generate\_bag\_of\_words($s_{i}.au_{j}$)
               \ENDIF
       \ENDFOR
       \FOR {each $w_{s_{i}.tu_{j}}$ in $s_{i}.tu\_list$ }
               \STATE $bow_{s_{i}.tu_{j}}$ = generate\_bag\_of\_words($s_{i}.tu_{j}$)
       \ENDFOR

       \FOR {$s_{i}.au_{j}$ in $s_{i}.au\_list$}
               \FOR {each $w_{s_{i}.tu_{k}}$ in $s_{i}.tu\_list$ }
                       \STATE $ common\_words^{au_{j}}_{tu_{k}} $ =  $bow_{s_{i}.au_{j}}
\cap bow_{s_{i}.tu_{k}}$
                       \STATE $ remaining\_words_{s_{i}.tu_{k}}$  = $ tu_{s_{i}}$ - words
forming title of $w_{s_{i}.tu_{j}} $ - stop words
                       \FOR {each word $w$ in $ remaining\_words_{s_{i}.tu_{k}}$}
                               \STATE $s_{i}.au_{j}.score$ += count of $w$
                       \ENDFOR
               \ENDFOR
       \ENDFOR
\STATE print $s_{i}.au_{j}$ reverse sorted by $s_{i}.au_{j}.score$
\ENDFOR


\end{algorithmic}
\end{algorithm}

\pagebreak

\begin{algorithm}
\small
\caption{Find wiki articles (called from Bag of Words)}
\label{alg:findwikiarticles}
\begin{algorithmic}
\STATE \textbf{Description}: Given a string of words determine phrases
that may be titles of wikipedia articles
\STATE \textbf{Input}: a string of words $s$
\STATE $l$ = length($s$)
\STATE $result$ = $\phi$
\FOR{$i$ in 1 to $l$}
       \FOR{$j$ in $i$ to $l$}
               \STATE $sub\_string_{ij}$ += $s_i$ + $blank$
       \ENDFOR
       \IF{ $sub\_string_{ij}$ consits only stopwords}
               \STATE discard and continue to next interation
       \ELSE
               \STATE search wikipedia with $sub_string_{ij}$
               \STATE $result_{sub\_string_{ij}}$ = (displaytitle, url, categories,
redirects) for $sub\_string_{ij}$
       \ENDIF
\ENDFOR
\RETURN result
\end{algorithmic}
\end{algorithm}


\begin{algorithm}
\small
\caption{Disambiguate articles (called from Bag of Words)}
\label{alg:disambiguate}
\begin{algorithmic}
\STATE \textbf{Description}: Given a disambiguation page returns the
wikipedia article that is most relevant to setence being processed
\STATE \textbf{Input}: disambiguation page $p$,$tu_{s_{i}}$
\STATE extract all outlinks urls from the body of the page
\STATE form a dictionary $d$ using disambiguation element ($de$) and
the disambiguation description ($dd$) appearing adjacent to the $de$
\FOR {every $de$ in $d$}
       \STATE $de.ddscore$ = count content word overlap between $dd$ and
($tu_{s_{i}}$ - words in  $de$)
\ENDFOR
%\STATE form a dictionary $l$ using disambiguation element ($de$) and
%the lead section ($ls$) appearing as the first paragraph of the
%article in $de$
%\FOR {every $de$ in $l$}
%       \STATE $de.lsscore$ = count content word overlap between $ls$ and
%($tu_{s_{i}}$ - words in  $de$)
%\ENDFOR
%\STATE form a dictionary $c$ using disambiguation element ($de$) and
%the category list ($cl$) appearing attached with the article on $de$
%\FOR {every $de$ in $c$}
%       \FOR {every category in $cl$}
%               \STATE $de.clscore$ = count content word overlap between $cl$ and
%($tu_{s_{i}}$ - words in  $de$)
%       \ENDFOR
%\ENDFOR
%\STATE Reverse sort the $de$s in each method using the scores
%\STATE Use Bordas ranking or weighted Bordas to merge the ranks
\RETURN top ranked $de$
\end{algorithmic}
\end{algorithm}


%\begin{enumerate}
%\item Step I: Detection of wiki articles from $DU$, $AU$, $TU$.
%\begin {enumerate}
%\item For the $AU$s, we take the words as they appear in the output of T-verifier(mainly because most of them are single word). For $TU$ we use a basic exponential algorithm that takes all possible combinations of the content words.
%\item The default configuration of T-verifier generates a total of 5 $AU$s, without any ranking.  For each content word in a $AU$, or a combination of words in case the $AU$ consists of multiple content words, we check if there exists a wikipedia article. There may be three cases:
%\begin{enumerate}
%\item No article. Continue with next word or word combination. 
%\item One article. Go to next step
%\item More than one article. The page lands into a "disambiguation" page. We discuss this later. 
%\end{enumerate}
%\end{enumerate}
%\item We remove the html tags from the pages, and convert them into simple bag of words. Repetation of a word if any is retained.
%\item We select the following pairwise combination - a wikiarticle detected from $AU$, ($W_{au_{i}}$) and a wikiarticle detected from $TU$ ($W_{tu_{j}}$).
%\item We take the common words $c_{ij} = {w_{1}, w_{2}, \ldots}$ matched by regular expressions in these two bags.
%\item Since this is a regular expression matching we will have two different values for $c_{ij}$ = common($W_{au_{i}}$, $W_{tu_{j}}$) and $c_{ji}$ = common($W_{tu_{j}}$, $W_{au_{i}}$). This is explained below.
%\item In this collection of common words, $c_{ij}$, we search each of the content words of the $TU$, not included in the title of $W_{tu_{j}}$ 
%\item We observe the maximum number of matches in all of such interesctions and use the count to rank the $AU$-s generated by T-verifer. 
%\end{enumerate}
%
%
%\paragraph{Handling Disambiguation}
%For the testing that we have done with the five problematic sentences, we manually first used the disambiguation page itself in the above process. But as expected, it did not yeild good results. We are experimenting with the following ideas for disabmigutation.
%\begin{enumerate}
%\item Apply the above steps for each of the page linked from the disambiguation page and get the one which gives the maximum count
%\item Use the heading under which it appears in the disambiguation page, the one sentence summary appearing adjacent to the entry in the disambiguation page, and the "Categories" under which a particular article has been tagged.
%\end{enumerate}
%For this report, we manually checked the disambiguation pages by searching them for content words. This significantly improved the results.
%
%\paragraph{Word matching}
%We found that the intersection of the two bags of words, $W_{au_{i}}$ and $W_{tu_{i}}$ produced different results based on the ordereing of the articles while performing the intersection operation. This is because the regular expression match finds the maximal match. Lets consider that the first file, $W_{au_{i}}$ has "invent", and the second file, $W_{tu_{i}}$ has "invented", and "inventor". So when we pick a word in $W_{au_{i}}$ and try to match words in $W_{tu_{i}}$, we will find 2 matches. However, the words from second file, both "invented", and "inventor" will not find any matches in ($W_{au_{i}}$). Taking both way intersections will ensure we do not miss out different morphological variations of the same word appearing in the context common to the both articles.

\paragraph{Example}
Detail working of Bag of Words (Algorithm 1) for following sentence is given below:

\emph{Les Paul invented the electric guitar}

For this sentence, the alternative units are les paul, gibson les, llyod, leo, adolph rickenbacker. At first, we generate all possible k-grams from the topic unit. The generated k-grams are following:

['invented', 'Invented', 'invented the', 'Invented The', 'invented the electric', 'Invented The Electric', 'invented the electric guitar', 'Invented The Electric Guitar', 'the', 'The', 'the electric', 'The Electric', 'the electric guitar', 'The Electric Guitar', 'electric', 'Electric', 'electric guitar', 'Electric Guitar', 'guitar', 'Guitar'] 

Now for each k-gram we find relevant wikipedia page. We will not get any wikipedia page for irrelevant k-gram.  Moreover, we may get a page directly or we may need to disambiguate. Following are the all relevant pages. The False in the second column means there is no ambiguation and True means we need to disambiguate.

\url{http://en.wikipedia.org/wiki/Invention}, False\\
\url{http://en.wikipedia.org/wiki/The_Electric}, True \\
\url{http://en.wikipedia.org/wiki/Electric_guitar}, False\\
\url{http://en.wikipedia.org/wiki/Electricity}, False \\
\url{http://en.wikipedia.org/wiki/Electric_guitar}, False \\
\url{http://en.wikipedia.org/wiki/Guitar}, False

For the above pages, we need to disambiguate for one page only and that is \url{http://en.wikipedia.org/wiki/The_Electric}. We described earlier that we look into the count of overlap between topic unit words and disambiguation link description words. For this disambiguation there is no overlap and so we do not need to process this page further. Hence the final set of $n$ pages for the topic unit are following:

\url{http://en.wikipedia.org/wiki/Invention} \\
\url{http://en.wikipedia.org/wiki/Electric_guitar} \\
\url{http://en.wikipedia.org/wiki/Electricity} \\
\url{http://en.wikipedia.org/wiki/Electric_guitar} \\
\url{http://en.wikipedia.org/wiki/Guitar}

In the next step, we find relevant Wikipedia page for each of the alternate units. There are no relevant Wikipedia page for  gibson les and llyod. Hence we do not process these alternative units further. For the remaining three alternative units, there is no ambiguation for les paul and adolph rickenbacker. The corresponding pages are following:

\url{http://en.wikipedia.org/wiki/Les_Paul}\\
\url{http://en.wikipedia.org/wiki/Adolph_Rickenbacker}

However we need to disambiguate for the page corresponding to Leo:

\url{http://en.wikipedia.org/wiki/Leo}

After disambiguation for Leo using word overlap between description and topic unit words, we get following page:

\url{http://en.wikipedia.org/w/index.php?action=raw&title=Leo_(constellation)}

Now, we need to count word overlap for each of the pages for les paul, adolph rickenbacker, leo with all pages for the topic unit and take sum of the overlap to produce the ranking of alternate units. So we generate bag of words for pages corresponding to all alternative units and also all the pages for the topic unit. 

Finally, for each alternate unit page, we count word overlap between alternate unit page and all topic unit pages and take sum of them. Now, we have a value associated with each alternate units that we are using for the ranking of the alternate units. Total count value for all alternate units and corresponding ranking is given below:

231 Les Paul \\
143 Adolph Rickenbacker \\
0 Leo

From this ranking we can clearly state that Les Paul is the correct answer. 



%A description of the above steps applied to the five problematic sentences
%\begin{enumerate}
%\item Sentence 1: Les Paul invented the electric guitar.
%\begin{enumerate}
%\item AU: Les\_Paul, Gibson Les, Leo, Llyod, Adolph Rickenbacker. 
%\item Wiki articles detected from AU($W_{au_{i}}$): Les\_Paul, Leo (disambiguation page), Adolph\_Rickenbacker 
%\item Wiki articles detected from TU($W_{tu_{i}}$): The\_guitar, The\_Electric\_guitar, Electric\_guitar, invented Invention 
%\end{enumerate}
%
%
%
%\item Sentence 2: Tom Hanks is the lead actress of the movie Sleepless in Sattle.
%\begin{enumerate}
%\item AU: hanks meg, meg ryan, tom hanks, nora, sam
%\item Wiki articles detected from AU($W_{au_{i}}$): Meg\_Ryan, Tom\_Hanks, Nora(Disambiguation), Sam(Disambiguation page) 
%\item Wiki articles detected from TU($W_{tu_{i}}$): Sleepless\_in\_Seattle, Lead, Lead-in, Leading\_actor(automatically redirected from Leading actress), Movie(automatically redirected from Film), Sleepless(disambiguation page), Seattle(lands on the correct page, though there is a disambiguation page).
%\end{enumerate}
%
%\item Sentence 3: Apollo was the first spacecraft on the moon.
%\begin{enumerate}
%\item AU: apollo, land, landing, luna
%\item Wiki articles detected from AU($W_{au_{i}}$): Apollo, Land(disambiguation page), Landing(disambiguation page), Luna(disambiguation)
%\item Wiki articles detected from TU($W_{tu_{i}}$): Fisrt(disambiguation page), Moon, Spacecraft.
%\end{enumerate}
%
%\item Sentence 4: english is the primary language of the philippines.
%\begin{enumerate}
%\item AU: english, filipino, spansih, education, history
%\item Wiki articles detected from AU($W_{au_{i}}$): English disambiguation page), Filipino(disambiguation page), Spanish(disambiguation), Education, History
%\item Wiki articles detected from TU($W_{tu_{i}}$): Primary (disambiguation page), language(disambiguation page), First\_Language (automatically redirected from Primary Languge), Philippines.
%
%\end{enumerate}
%
%
%\item Sentence 5: Michael Phelps is the fastest swimmer in the world
%\begin{enumerate}
%\item AU: michael, long, ernest, sullivan, alexander
%\item Wiki articles detected from AU($W_{au_{i}}$): Michael, Alexander, Sullivan(disambiguation page), Long(disambiguation page), Ernest(disambiguation page) 
%\item Wiki articles detected from TU($W_{tu_{i}}$): Fastest, Swimming(sport) (automatically redirected from Swimmer),World.
%
%\end{enumerate}
%
%
%\end{enumerate}
%
%Please refer to the hand out analysis of the results.


\subsection{Sentence Splitting}

The main idea behind this ranking algorithm for alternative units is that Wikipedia should contain content words from doubt statement in the same sentence because of the similarity in the context. Details description of the algorithm is given below.


\begin{algorithm}
\small
\caption{Sentence Structure (Ranking Algorithm 2)}
\label{alg:SentenceStructure} 
\begin{algorithmic}
\STATE Search google with topic unit
\STATE take first Wikipedia page from google search result
\STATE Extract all sentences from the Wikipedia page
\FOR{each alternate unit}
	\FOR{each sentence from Wikipedia page}
		\IF{alternate unit is found in the sentence}
			%\IF{some content word found in the sentence}
			%	\STATE return true
			%\ELSE
			%	\STATE return false	
			%\ENDIF
			\STATE count [alternate unit]= no of intersection of content words from topic unit and the sentence
		\ENDIF
	\ENDFOR
\ENDFOR		
\STATE rank the alternate units using descending order of count[alternate unit]

\end{algorithmic}
\end{algorithm}

\paragraph{Examples}
Detail working of Sentence Structure (Algorithm 2) for following sentence is given below:

\emph{Les Paul invented the electric guitar}

For this sentence the alternative units are les paul, gibson les, llyod, leo, adolph rickenbacker. The top wikipedia page from google search is \url{http://en.wikipedia.org/wiki/Electric_guitar}. So we download this page. Convert it to text from html and split into sentences. Then we match each alternate unit with all the sentences to see if there is any intersection with the alternate unit. We found intersection for the alternate units les paul, gibson les, llyod, and adolph rickenbaker but not for leo. Hence leo get a score of zero and we process other alternative units further. In the next step, we find intersection between content words or topic unit and matched sentences for alternate units found in the previous step. We count no of words that are overlapped and rank alternate units according to this count value. Count of the content word overlap is given below.

3 les paul\\
1 gibson les\\
0 llyod\\
0 leo\\
0 adolph rickenbacker

 It shows that we have 3 content word intersection for les paul, 1 word intersection for gibson les and 0 for all other alternate units. This ranking is the final truth or confidence ranking for all alternate units. 
 
 
 \subsection{Result Summery}
 We are finding ranking for five alternate units for each doubtful sentences using both algorithm 1 and algorithm 2. Then we are taking union of ranking for from both algorithm and producing the final ranking for all the sentences. Appendix A discussed ranking done by algorithm 1 and appendix B discusses ranking done by algorithm 2. Finally, we are combining both of these ranking using union and producing final ranking, which is discussed at the Appendix C. Our final ranking is following:

Total correct sentences from T-verifier:  $43$ \\
Correct output by both algorithm:  $23$ \\
Very close to correct output by both algorithm:  $8$\\
Close to correct output by both algorithm:  $7$ \\
Incorrect output by both algorithm:  $5$ \\


Although the overall result is promising, there are some difficulties because of disambiguation in algorithm 1. These difficulties are described below:

\begin{itemize}
\item \emph{Handling case of article titles:} First letter of first word in Wikipedia article title is case insensitive and all the remaining letters are case sensitive. This creates problems for extracting relevant pages from Wikipedia. For example, to find the page for "Big Mac", we can't find the page if we supply "Big mac" because 'M' of "mac" needs to be capital. But for "Sleepless in Seattle" we need to use small 'i' in the "in" for extracting correct page.

\item \emph{Problem with finding relevant disambiguation page:} We are using word overlap between words of topic unit and description of disambiguation link to find disambiguated page. But this method is not powerful enough to get appropriate disambiguation page and we are getting lot of irrelevant pages. So the bag of words generated for these irrelevant pages are not good as feature and we are getting bad result. Hence we need better disambiguation technique to deal with this issue and improve the performance of our algorithm further.  
\end{itemize}

 
 
 %\paragraph{Examples}
%Examples of the algorithm described above is discussed below. The algorithm 2 produce perfect result for three of the five sentences. But it struggles with the remaining two sentences. However, the algorithm 2 primarily augment the algorithm 1 and add strength to the results from algorithm 1. Hence they work better together and produce overall better output.
%
%\paragraph{Tom Hanks was the lead actress  int move 'Sleepless in Seattle'}
%The alternative units for this sentence are "Tom Hanks", "Meg Ryan", "Hanks Meg", "Nora", and "Sam". Here the sentence containing "Tom Hanks" contain the word actor but not actress. So the algorithm classify it as false. But the sentence containing "Meg Ryan" has the word actress and hence classify it as true. For other alternative units, we don't even get any sentences containing the alternative unit. So the algorithm produce an unambiguous single true statement for this sentence.
%
%\paragraph{Les Paul invented the electric guitar}
%The alternative units for this sentence are "Les Paul", "rickenbacker", "Gibson", "Leo", and "Lloyd". Now there is inherent ambiguity about the true inventor of the electric guitar. On reading the articles related above, there is no information that Rickenbacker actually inventing the electric guitar. He was a founding member of the Rickenbacker company that produces electric guitar. Les Paul on the other hand was a pioneer in designing and developing of what a prototype. Moreover, some of the categories attached with the Les Paul page are American musical instrument makers, Guitar makers, Inventors of musical instruments, National Inventors Hall of Fame inductees. In comparison Adolph Rickenbaker page has only one guitar related category - Guitar stubs, meaning the article is stuck in content.
%
%\paragraph{Luna 2 is the first spacecraft on the moon}
%The alternative units for this sentence are "Luna 2", "Apollo", "Land", "Landing", and "Nasa". Our algorithm returns true for both Luna 2 and Apollo and return false for all others. Now, both Luna 2 and Apollo are in reality true considering the facts that Luna 2 was the first unmanned spacecraft and Apollo was the first manned spacecraft. Hence, we can't say one of the Luna 2 or Apollo as false if farther information is not given. So algorithm 2 can produce correct result for this sentence also.
%
%\paragraph{English is the Primary Language of the Philippines}
%The alternative units for this sentence are "English", "Filipino", "Spanish", "Education", and "History". Our current algorithm struggle with this sentence because of occurrence of content words and alternative units in the same sentence for all the alternative units. So it classify all of them as true and assign same weight to all of them. However, as our algorithm 1 can rank the alternative units in correct order, merged rank from algorithm 1 and algorithm 2 is still correct and produce overall correct result. 
%
%\paragraph{Sullivan is the fastest swimmer in the world}
%The alternative units for this sentence are "Sullivan", "Michael phelps", "ALexander", "Long", and "Ernest". Similar to the previous sentence, the algorithm 2 can not produce good ranking for for this sentence. However, our algorithm 1 produces correct ranking and together they produce overall correct result.
%
%\subsection{Rank merging}
%This ranking procedure bolsters the result in the previous algorithm always without any exception. On observing the five examples above, we expect a combination of the two algorithms will give us a proper ranking of the alternate units for proper truth verification.
%
%

\section {Alternative methods that are explored}


%\begin{figure}
%  \centering
%  \subfloat[System
%  overview]{\label{fig:System}\includegraphics[width=0.85\textwidth]{system.pdf}}
%  \caption{System overview}
%  \label{fig:system}
%\end{figure}
%
%
%\subsection{Description of extraction algorithm}

For disambiguation among the alternative statements, Wikipedia is generally used
as an authoritative source. On the other hand DBpedia, Freebase have organized the
massive amount of data in a searchable fashion e.g. DBpedia uses SPARQL endpoint,
Freebase uses MQL api. Open source implementation of Python wrappers exist for
both the interfaces exist and appear to be mature enough for our needs.

\subsection{Freebase} 
Freebase has information about approximately 20 million Topics, each one having a
unique Id, which can help distinguish multiple entities which have similar names,
such as Henry Ford the industrialist vs Henry Ford the footballer. Most of the
topics are associated with one or more types\cite{freebasetype} (such as
people, places, books, films, etc) and may have additional properties like "date of birth" for a person
or latitude and longitude for a location. Freebase not only contains data from
the Wikipedia but also other sources; users can submit data to the Freebase
datastore and expand it in richness. We tinkered with the api\cite{freebaseapi}
and it appeared to be the most viable starting point for the project.

\subparagraph{Motivational Example}

\begin{lstlisting}[label=some-code,caption=Minimal code to Freebase]

import freebase
import pprint

query = [{
  "a:starring": [{
    "actor": "Meg Ryan"                                                       
  }],
  "b:starring": [{                                                            
    "actor": "Tom Hanks"
  }],
  "type": "/film/film",
  "*": [],
}]  
    
pp = pprint.PrettyPrinter(indent=4)
result = freebase.mqlread(query)
    
print "Movie names & their various forms"
    
    
for i in result:                                                              
        pp.pprint(i["key"])                                                   
                
\end{lstlisting}
\begin{lstlisting}[label=output,caption=Cleaned Output]

Movie names & their various forms
[   '158982',
    'You$0027ve_Got_Mail',
    '18171032',

     ...
    'E-m$0040il_f$00FCr_Dich',
    'youve-got-mail']
[   '176489',
    'Joe_Versus_the_Volcano',
    'Joe_Vs$002E_The_Volcano',
    'Brain_Cloud',
     ...
    '2327353',
    'joe-versus-the-volcano']
[   '226198',
    'Sleepless_in_Seattle',
    'Sleepless_In_Seattle',
     ....
    '169146',
    '106482',
    'Insonnia_d$0027amore',
    '62812',
    'Schlaflos_in_Seattle',
    'sleepless-in-seattle'\]

\end{lstlisting}

The above results show how the three movies starring Tom Hanks and Meg Ryan.
When we query Google with Tom Hanks and Meg Ryan, the top result is a page from
Answers.com where a user has asked which are the movies where the two actors
appear together, and the answer lists these three movies namely - ``Joe versus
the Volcano'', `` Sleepless in Seatle'' and ``You\'ve got Mail''. A quick lookup
of the Wikipedia and IMDB pages also confirm the same. 


\subsubsection{Use of Freebase}

For all the 50 sentences mentioned in the original paper we tried the default POS tagger that comes with the Natural Language toolkit along with NE chunker, Binary NE Chunker and the IEER NE Chunker. None of the yeilded good results. So we used the Illinois named entity extractor from UIUC, which gave comparitively better results primarily because its database is built from various sources like the Wikipedia, Brown Hierarchical Word Clusters etc. 

\begin{itemize}
\item Correctly tagged 19
\item Partly correct 14	
\item Wrong/no identification 12
\end{itemize}



Consider one of the following sentences:

\emph{"Tom Hanks was the lead actress in the movie Sleepless in Seattle"}

Tom/NNP Hanks/NNP was/VBD the/DT lead/NN actress/NN in/IN the/DT movie/NN Sleepless/NNP in/IN Seattle/NNP
Phrases and Named Entities

PERSON:
    Tom/NNP
PERSON:
    Hanks/NNP
GPE:
    Seattle/NNP

Content words for this sentence are "Tom Hanks", "lead", "actress", "movie", "Sleepless in Seattle". 

While "actress" is a domain in freebase, it does not contain anythingi yet. So we look into the synset of the word "actress" from wordnet, which includes \emph{"female actor"}.

Now for the noun phrase \emph{"Sleepless in Seattle"}, we can generate "id" for the query as "sleepless in seattle". But this id will be associated with many properties. To select the relevant property we can use synset obtained from the actress. And this synset has {\em actor}, which is one of the property for id {\em "Sleepless in Seattle"}. Hence the Freebase query can be following:

\begin{lstlisting}


[{
  "id" : "/en/sleepless_in_seattle"
  "/film/film/starring" : [{ "actor" : null }]
}]


Now the result of this query returns following output:


  "code":          "/api/status/ok",
  "result": [{
    "/film/film/starring": [
      {
        "actor": "Tom Hanks"
      },
      {
        "actor": "Meg Ryan"
      },
      {
        "actor": "Bill Pullman"
      },
      {
        "actor": "Rosie O'Donnell"
      },
      {
        "actor": "Rob Reiner"
      },
      {
        "actor": "Victor Garber"
      },
      {
        "actor": "Gaby Hoffmann"
      },
      {
        "actor": "Carey Lowell"
      },
      {
        "actor": "David Hyde Pierce"
      },
      {
        "actor": "Ross Malinger"
      },
      {
        "actor": "Frances Conroy"
      },
      {
        "actor": "Rita Wilson"
      }
    ],
    "id": "/en/sleepless_in_Seattle"
  }],
  "status":        "200 OK",
  "transaction_id": "cache;cache03.p01.sjc1:8101;2011-03-09T05:09:44Z;0032"
}

\end{lstlisting}

One of the actors in this result set is "Tom Hanks" that matches with our content word "Tom Hanks" in the given sentence. Now as we know earlier that actress means female actor, we can use the keyword female to find the fact that female is type of gender and Freebase id of "tom hanks" has a property gender associated with it. So we can formulate following query.

\begin{lstlisting}

[{
  "id" : "/en/tom_hanks"
  "/people/person/gender" : {}
}]

The result of this query is following:

{
  "code":          "/api/status/ok",
  "result": [{
    "/people/person/gender": {
      "id":   "/en/male",
      "name": "Male",
	.
	.
	.
}	

\end{lstlisting}

Here the gender is Male, which contradicts with our gender female. Hence we can decide that this statement is false. 

For finding the true statement i.e. the actress we can use all actors obtained in the first query result and form second query with their names and output the truthful sentence if we get female as the gender.

\subsection{Dbpedia}
DBpedia is a similar project to Freebase, but it focuses mainly on the content
available from Wikipedia. It scores in being precisely importing the data from
the info boxes in Wikipedia pages, but at this stage it does not seem to be
offering anything additional over Freebase \cite{freebasedbpedia}. We are yet to
explore its programmatic interface \cite{dbpediaapi}.


\subsection{Yago}
YAGO is a semantic knowledge base with over 900,000 entities (like persons,
organizations, cities, etc.) and uses Wikipedia and Wordnet as its main source of
information. We are yet to explore the programmatic interfaces it provides and
how we can use it for the project.



\subsection {Building queries from the data supplied by the user}

Formulating a proper Freebase query is for our specific purpose is a different process than the standard way of querying a search engine that does full text search on text documents. We start by introducing the  various abstraction levels associated with the freebase data.
\begin{itemize}
    \item  A {\em type} is a conceptual container of related {\em properties} commonly needed to describe a certain aspect of a {\em topic}.
    \item  A {\em topic} can be assigned one or more types (the default type being /common/topic)
    \item  As {\em properties} are grouped into {\em types}, {\em types} are grouped into {\em domains}.
    \item  {\em Domains, types}, and {\em properties} are given IDs in a {\em namespace/key} hierarchy.
    \item  Common well-known topics are given IDs in the /en namespace, which are human-readable English strings.
    \item  {\em Topics} are uniquely identified within Freebase by {\em GUIDs}.
    \item  {\em Properties} are {\em multi-value} by default, and multi-value properties and single-value properties can be queried in the same way.
\end{itemize}
In order to transform a sentence to a freebase query we have to one to one map a content word from the sentence($TU$ plus $DU$) to the above mentioned abstraction. In other words, the process involves identifying the contextual meaning of the content words. Although this is pretty intuitive when we do it manually, trying to achieving this programmatically is one the challenging aspect of the project. One way of doing it is using a part of speech taggers, along with chunk extraction and named entity recognition. (details in next section) 

The key point of distinction is that this result set is the set of records from a hierarchical database. We can not stuff in every word from the topic units into a query to freebase, as MQL(metaweb query language) is Query By Example language, and has a rigid structure which is not immediately obvious given a sentence in natural langage. We incrementally build a query $Q$ starting from with one word $w_{i}$ from the word list $L$ extracted from the $TU$. Let the results associated with $q_{w_{i}}$ be ($R_{w_{i}}$). Initially Q = $\{q_{1}=w_{i}\}$

 The following are the possible cases
\begin{itemize}
\item No results - In this case we get the synset from Wordnet $S_{w_{i}}$ and repeat the search with each word in the synseti $w_{j}^{s}$.
\item If there is no match with the word or its synset, we reject $w_{i}$ from the query $Q$ and move on to the next word in $L$ and repeat the process.
\item If $R$ is not empty, we retain the $w_{i}$ or $w_{j}^{s}$ in $Q$. Then we take the each of the remaining words $w_{j}$ from $L$ and $S_{w_{j}}$ and search in $R_{w_{i}}$. If $w_{j}$ or a synonym of it $w_{j}^{s}$ is found to occur in the resulti, we augment $Q$ with $w_{j}$ (or $w_{j}^{s}$). So $Q$ now becomes $Q =\{q_{1}=w_{i}, q_{2}=w_{j}\}$ or $\{q_{1}=w_{i},q_{2}=w_{j}^{s}\}$ 
\item With the new $Q$ we again query Freebase and repeat the above steps.
\item We terminate when all the words (and in their synsets) in $L$ have been substituted. This allows us to form the most appropriate query $Q$ from the $TU$. Note though this is essentially a breadth first search search of the graph, we would not be traversing very deep (though the branching factor can be pretty high) because of the small number of content words in $TU$ and their synsets.
\item If the result returned by this query $Q$ contains the $DU$, we can say with a good degree of confidence that the statement is true.    
\end{itemize}
%\begin{align*}
%q_{i} = \{{TU, AU_{i}, t_{AU_{i}}} \} \qquad \mbox {where $i = 1 \cdots n$} \\
%\end{align*}
%where $n$ is the number of alternative units generated by the first phase of
%the existing system. By quering the various ontologies described above we will
%get results which might have the following cases:
%
%\begin{align*}
%   freebase(q_{i}) &= \phi \\
%    = r_{i}
%\end{align*}
%


\subsection{Wikipedia API}

\label{March9to29}
Contrary to our prior report, Wikipedia does have a very rich API, which the wiki software, Mediawiki provides. Of the various features that this API provides there are two searching mechanisms. 

\subsubsection{Opensearch Protocol}
The first one is Opensearch protocol, which gets pages whose name case-insensitively match a given string. When default limit(10) is reached, results are ordered by number of incoming links. For example if we search for Forrest Gump, we will get:

\begin{lstlisting}[label=Opensearch Protocol, caption=Result using Opensearch]
    * "Forrest Gump"
          o "Forrest Gump"
          o "Forrest Gump (character)"
          o "Forrest Gump (novel)"
          o "Forrest Gump (soundtrack)"
          o "Forrest Gump – Original Motion Picture Score"
          o "Forrest Gump (disambiguation)"

\end{lstlisting}

This to a certain extent provides some semantic information attached alongwith the term.

\subsubsection{Fulltext search}
This provides a richer resultset, which syntactically resembles as the results returned for query on a web search engine. However, the interpretation of the returned results and the methods to analyse it has to significantly different. A real world example might make this distinction more clear. Searching the web is more like asking which books in the library has information on a particular topic, but full text search on wikipedia is more like pulling out a single volume of one's favourite encylopedia and searching the index pages to find if there is an article on this topic. So each article has a definite focus and it is closely defined by its title. Majority of the wikipedia pages adhere to some structure, which might reveal more than the text that is in there for the article. For example the interwiki links, the See also links etc. point towards related topics. Before exploring those areas, we first focus on the various aspects that are immediately available from the api:

\begin{enumerate}
\item    srinfo – What metadata to return. Type: one of totalhits, suggestion
\item    srlimit – How many total pages to return. Type: limit
\item    srnamespace – The namespace(s) to enumerate. Type: namespace
\item    sroffset – Use this value to continue paging (return by query). Type: integer
\item    srprop – What properties to return:
\begin{enumerate}
\item    size - Adds the size of the page in bytes
\item    wordcount - Adds the word count of the page
\item    timestamp - Adds the timestamp of when the page was last edited
\item    score - Adds the score (if any) from the search engine
\item    snippet - Adds a parsed snippet of the page
\item    titlesnippet - Adds a parsed snippet of the page title
\item    redirectsnippet - Adds a parsed snippet of the redirect
\item    redirecttitle - Adds a parsed snippet of the redirect title
\item    sectionsnippet - Adds a parsed snippet of the matching section
\item    sectiontitle - Adds a parsed snippet of the matching section title
\item    hasrelated - Indicates whether a related search is available
\end{enumerate}
\item    srredirects – Include redirect pages in the search. Type: bool
\item    srsearch (required) – Search for all page titles (or content) that has this value. Type: string
\item    srwhat – Search inside the text. Searching titles is disabled in Wikipedia.
\end{enumerate}


\subsection{Problem transformation - Recognizing Text Entailment}
While a thorough experimentation needs to be done in how to utlize all these parameters to do a better extraction of the underlying semantics, we realize limiting the knowledge base to Wikipedia, reduces the problem to an instance of Recognizing Text Entailment (RTE). Over the last few years amazing progress has been made in this track, and the state of the art algorithms are quite complicated to be implemented with in this short time frame. We start off with a simple idea for RTE, and list some experimentation that we plan to do ahead. 

The main problem of RTE is that given a Hypothesis(H) and Text(T), the algorithm has to detect if T entails H.

T:The sale was made to pay Yukos' US\$ 27.5 billion tax bill, Yuganskneftegaz was originally sold for US\$ 9.4 billion to a little known company Baikalfinansgroup which was later bought by the Russian state-owned oil company Rosneft .

H:Baikalfinansgroup was sold to Rosneft.

The above example is taken from Recognizing Textual Entailment (RTE) 3 Challenge Corpora. The correct answer in this case, (i.e. yes T entails H) is easy for humans to comprehend, but obiviously the greatest challenging task to do programmatically.

The basis of the transformation is that each $DS$ now becomes a Hypothesis(H) and the wikipedia article the Text(T). 

\subsubsection{With or without the doubt unit}

The original approach left out the doubt unit in order to not bias the returned results. However, in this case it might actually be beneficial. We can also go the other way, that is using the $DU$ to search article and then check in that article if there is sufficient intersection with the remainder of the doubtful statement. While this may work well for names and places, this would not work out for dates enforcing us to have separate rules attached to different data types. We have only tried without the DU right now.

\subsubsection{Without DU}
We remove the doubt unit (DU) and stop words from the topic unit and use the remaining key words to do a full text search. The results returned by Lucene, search engine that powers these searches are very accurate. But our task is much more complex, and it requires even finer analysis of the result. 

Of the various properties that a returned result may be decorated with, the two most important ones are:
\begin{itemize}
\item titlesnippet - This is probably the most important category of all. If the doubt unit is located here then it would mean that there is a wikipedia page for the doubt unit, and the text contains keywords from the doubtful statement. This is the strongest indication that that the statement might be true.
\item snippet - This is the SRR in this case, that is formed by the concatenation of parts from three sentences that surround matched query keywords in the article content. The important thing to consider over here are the distaces between two such sentence parts and the number of matches each part includes. For a long page, there may be located at two very different areas in the page and be about very different contexts. In order to handle this we can take a weighted distance measure that takes the number of words between two matching sentence parts $0.33*number of matches in a sentence part/(length of the sentence part*length of document)$

\end{itemize}

\begin{lstlisting}[label=pseudo-code,caption=Feature extraction initial steps]


snippet_split_weights = {}
snippet_splits = split snippets by '<b>...</b>' 
for snippet_split in snippet_splits:
        snippet_split_len = length(snippet_split)
        snippet_split_match_count = count number of matches in snippet_split
        snippet_split_weights[snippet_splits.index(snippet_split)] 
		= snippet_split_match_count/snippet_split_len
snippet_weight = 0
for snippet_split_weight in snippet_split_weights.values():
        snippet_weight +=snippet_split_weight
snippet_weight= 0.33*snippet_weight

#TITLE
title_match_count = count all matches in result['titlesnippet']
title_len = length(result['title'])
title_weight = title_match_count/title_len

#TODO need to determine appropriate wieghts
overall_result_weight = (title_weight+snippet_weight)/2


if regex_tokenize:
        tokenizer = RegexpTokenizer('([A-Z]\.)+|\w+|\$[\d\.]+')

        snippet_tokens = set(tokenizer.tokenize(snippet))
        title_tokens = set(tokenizer.tokenize(result['title']))
        doubt_unit_tokens = set(tokenizer.tokenize(doubt_unit))
else:
        snippet_tokens = set(lower case the snippet and tokenize by space)
        title_tokens = set(lower case the title and tokenize by space)
        doubt_unit_tokens = set(lower case the doubt_unit and tokenize by space)


found = False

#If the match is found in the snippet
if snippet_tokens.intersection(doubt_unit_tokens):
        print "S",';',title_weight,';',snippet_weight,';',overall_result_weight
        found = True

#if the match is found in the Title
if title_tokens.intersection(doubt_unit_tokens):
        print "T",';',title_weight,';',snippet_weight,';',overall_result_weight
        found = True

#If no match is found
if title_tokens.intersection(doubt_unit_tokens):
        print "N",';',title_weight,';',snippet_weight,';',overall_result_weight
        found = True


\end{lstlisting}


As for the rest of the properties like redirectitles, redirectsnippets, sectiontitle, sectionsnippets did not return values that seem to be of immediate help. However, they made find their use in generating alternative units. We have not yet experimented with them yet.

Currently the code that we have written only checks for presence of the doubt unit in each of the above mentioned property, for the fifty sentences that were there in the original paper. 

The following are the immediate concerns 
\begin{itemize}
\item Better matching: We tried two ways to match the DU-s in the returned results, one a conservative approach that would try to tokenize so that abbreviations like "U.S.A" and monetary amounts like "\$23.00" are kept as tokens. In the more relaxed approach the tokens were all lowercased and split by spaces. This obviously is the most crucial part of the entire process and it appears we should have separate strategy based on the data type of the doubt unit.
\item Building the classifier: We got the data from TREC 9, which is in a question answer format and have finished converting 100 of the 711 sentences all to statement form with correct answers. Once we have some more sentences labeled we will use it to train a classifier from the features extracted above.
\end{itemize} 

%\subsubsection{Data Description}
%The attached file shows the data collected for each sentence from wikipedia. We take the top 10 results returned by searching wikipeida, and calculate the values mentioned above. "S" denotes that $DU$ appears in the snippet, "T", shows that it appears in the Title, and "N" means the $DU$ was not found anywhere. The other values are separated by ';' are title weight,snippet weight,overall result weight.
% 
\subsection{Use of answer.com}
We found that answer.com also contains the correct answers to the for the doubt sentences in almost of all the cases. The precise Q\&A format of closely matching the sentences excites us about the possibilities of using the above mentioned strategies for this site. A lot of domain specific sites (like stackexchange.com, quora.com) have become very popular since 2009, which deviate from the traditional forums in the sense that the user generated content is voted, summarised and exposed to a programmatic interface. 





%After getting the wikipedia page we can convert the html file into text file and then we can separate all the sentences in different lines. The sentence is the part of the whole text that exist between two full-stops. Another important observation is that the relevant information will be within the same sentence in the question-answer type sentences almost all the time. So we can match the content words to the sentences extracted from Wikipedia page and verify the truthfulness of the sentence. 

%For the example sentence above, after processing the Wikipedia page and matching by inventor we get following two sentences:
%\begin {itemize}
%\item \emph{"Commercial production began in late summer of 1932 by Electro-Patent-Instrument Company Los\_Angeles, a partnership of Adolph\_Rickenbacker, PaulBarth and George\_Beauchamp, the inventor"}

%\item \emph{In a morecontemporary style, Little Willie Joe, the inventor of the Unitar, had a rhythmand\_blues instrumental hit in the 1950s with "Twitchy", recorded with the ReneHall Orchestra}
%\end{itemize}




%\section{Conclusion}
%It this paper, we described current system for truthfulness verification of statements found in the web called T-Verifier and described the possible improvements to the current system. We will primarily use authentic information sources such as Wikipedia and Ontologies extracted from Wikipedia such as FreeBase, DBPedia, and YOGA to found the truthfulness of doubtful statements.  



\bibliographystyle{plain}
\bibliography{ref}

\end{document}

